# 递归算法实现的找零
# 非常低效
def recMC(coinValueList, change):
    minCoins = change
    if change in coinValueList:
        # 最小规模, 直接返回
        return 1
    else:
        tempValueList = [c for c in coinValueList if c <= change]
        for i in tempValueList:
            # 规模减小并调用自身
            numCoins = 1 + recMC(coinValueList, change-i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins

# print(recMC([1,5,10,25], 11))

# 改进的递归找零, 使用了缓存查表的方法
def recDC(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        knownResults[change]=1
        return 1
    elif knownResults[change] > 0:
        return knownResults[change]
    else:
        tempValueList = [c for c in coinValueList if c <= change]
        for i in tempValueList:
            numCoins = 1 + recDC(coinValueList, change-i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins
    return minCoins

print(recDC([1,5,10,25], 11, [0]*12))
